#ifndef __queue_h__
#define __queue_h__

#include <iostream.h>
#include <string.h>

template < class C > class queue {
public :
   enum { MAX_QUEUE = 100 } ;
   queue( queue & q , int start ) {
      last = -1 ; 
      first = 0 ; 
      nelems = 0 ;
      numRetrieved = 0 ;

      int i = 0 ;
      C t ;
      while ( q.getElem( t ) ) {
         if ( i >= start ) {
            insert( t ) ;
         }
         i++ ;
      }       

      cPost( "queue" ) ;
            
   }
   queue() { 
      last = -1 ; 
      first = 0 ; 
      nelems = 0 ;
      numRetrieved = 0 ;
      cPost( "queue" ) ;
   }
   bool insert( C c ) { 
      nelems++ ; 
      last = ++last % MAX_QUEUE ; 
      q[ last ] = c ;
      cPost( "insert" ) ;
      return true ;
   } 
   bool empty() { return nelems == 0 ; }
   C getFirst() { 
      cPost( "getFirst" ) ;
      return q[ first ] ;
   } 

   C get( int i ) { 
      cPost( "get" ) ;
      return q[ ( first + i ) % MAX_QUEUE ] ;
   } 

   C extractFirst() { 
      nelems-- ; 
      int prec = first ; 
      first = ++first % MAX_QUEUE ; 
      cPost( "extractFirst" ) ;
      return q[ prec ] ;
   } 
   bool getElem( C & c ) {       
      if ( numRetrieved == 0 ) {
         curPos = first ;
      }
      else {
         curPos = ++curPos % MAX_QUEUE ; 
      }
      numRetrieved++ ;
      bool ok = numRetrieved <= nelems ;
      if ( ok ) {
         c = q[ curPos ] ;
      }
      else {
         numRetrieved = 0 ;
      }
      return ok ;
   } 
   int getNumElems() {
      return nelems ;
   }
private :
   int first ;
   int last ;
   int nelems ;
   C q[ MAX_QUEUE ] ;
   int curPos ;
   int numRetrieved ;
   void cPost( char * m ) { 
      bool ok = ( ( MAX_QUEUE + 1 + last - first ) % MAX_QUEUE ) == nelems ;
      if ( ! ok ) {
         cerr << "Postcondition failed in method queue:" << m << endl ;
      }
   }
} ;
#endif
